TNotes.leetcode

Appearance

0015. 三数之和【中等】

0015. 三数之和【中等】 ​

1. 📝 题目描述 ​

给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k，同时还满足 nums[i] + nums[j] + nums[k] == 0。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1, 0, 1, 2, -1, -4]
输出：[[-1, -1, 2], [-1, 0, 1]]

解释：

  • nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0。
  • nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0。
  • nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0。
  • 不同的三元组是 [-1, 0, 1] 和 [-1, -1, 2]。
  • 注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0, 1, 1]
输出：[]

解释：唯一可能的三元组和不为 0。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]

解释：唯一可能的三元组和为 0。

提示：

  • 3 <= nums.length <= 3000
  • -10^5 <= nums[i] <= 10^5

2. 🎯 s.1 - 排序 + 双指针 ​

svg

c
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume
 * caller calls free().
 */
int compare(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

int** threeSum(int* nums, int numsSize, int* returnSize,
               int** returnColumnSizes) {
    qsort(nums, numsSize, sizeof(int), compare);

    int capacity = 16;
    int** ans = (int**)malloc(capacity * sizeof(int*));
    *returnColumnSizes = (int*)malloc(capacity * sizeof(int));
    *returnSize = 0;

    for (int i = 0; i < numsSize - 2; i++) {
        // 跳过重复的数字
        if (i > 0 && nums[i] == nums[i - 1])
            continue;

        int left = i + 1, right = numsSize - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                if (*returnSize == capacity) {
                    capacity *= 2;
                    ans = (int**)realloc(ans, capacity * sizeof(int*));
                    *returnColumnSizes = (int*)realloc(*returnColumnSizes,
                                                       capacity * sizeof(int));
                }
                ans[*returnSize] = (int*)malloc(3 * sizeof(int));
                ans[*returnSize][0] = nums[i];
                ans[*returnSize][1] = nums[left];
                ans[*returnSize][2] = nums[right];
                (*returnColumnSizes)[*returnSize] = 3;
                (*returnSize)++;

                // 跳过重复的数字
                while (left < right && nums[left] == nums[left + 1])
                    left++;
                while (left < right && nums[right] == nums[right - 1])
                    right--;
                left++;
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    return ans;
}
js
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  const ans = []
  const len = nums.length

  nums.sort((a, b) => a - b) // 升序

  for (let i = 0; i < len - 2; i++) {
    // 跳过重复的数字
    if (i > 0 && nums[i] === nums[i - 1]) continue

    let left = i + 1
    let right = len - 1

    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right]

      if (sum === 0) {
        ans.push([nums[i], nums[left], nums[right]])

        // 跳过重复的数字
        while (left < right && nums[left] === nums[left + 1]) left++
        while (left < right && nums[right] === nums[right - 1]) right--

        left++
        right--
      } else if (sum < 0) {
        left++
      } else {
        right--
      }
    }
  }
  return ans
}
py
class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        nums.sort()
        ans = []
        n = len(nums)

        for i in range(n - 2):
            # 跳过重复的数字
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            left, right = i + 1, n - 1
            while left < right:
                s = nums[i] + nums[left] + nums[right]
                if s == 0:
                    ans.append([nums[i], nums[left], nums[right]])
                    # 跳过重复的数字
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    left += 1
                    right -= 1
                elif s < 0:
                    left += 1
                else:
                    right -= 1
        return ans
  • 时间复杂度：O(n2)，排序 O(nlog⁡n)，外层枚举 O(n)，内层双指针 O(n)，整体 O(n2) 主导
  • 空间复杂度：O(log⁡n)，排序递归栈空间（不计输出数组）

算法思路：

  • 先对数组升序排序
    • 作用 1：确保单调性
    • 作用 2：使相同元素相邻，便于去重
  • 固定成员 + 窗口收缩
    • 我们假定 i 指向的是三元组中的最小成员，left 指向的是三元组中的中间成员，right 指向的是三元组中的最大成员
    • 每次初始化窗口时固定窗口前边儿的第一个数 nums[i]（枚举 i 从 0 到 n-3），问题转化为在 i 后边儿的窗口中找两数之和等于 -nums[i]
    • 用左右双指针 left = i+1、right = n-1 收缩：三数之和 < 0 则 left++，> 0 则 right--，等于 0 则记录结果并跳过所有相邻重复值后再同时收缩
    • i 若与前一个元素相同则跳过，避免产生重复三元组

Discussions